#include <bits/stdc++.h>
using namespace std;

// 1.堆
// class Solution {
// public:
//     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//         priority_queue<int> q;
//         for(int i = 0; i < m; i++) {
//             q.push(nums1[i]);
//         }
//         for(int i = 0; i < n; i++) {
//             q.push(nums2[i]);
//         }
//         for(int i = m+n-1; i >= 0; i--) {
//             if(!q.empty()) {
//                 nums1[i] = q.top();
//                 q.pop();
//             }
//         }
//     }
// };

// 2.双指针
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = nums1.size() - 1;
        m--;
        n--;

        while (n >= 0) {
            while (m >= 0 && nums1[m] >= nums2[n]) {
                swap(nums1[i--], nums1[m--]);
            }
            swap(nums2[n--], nums1[i--]);
        }
    }
};